#include<iostream>
#include<unordered_set>

/*给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。
如果两个链表不存在相交节点，返回 null 。*/

struct Node
{
    Node* next;
    int val;
};
//解法1
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB)
 {
    std::unordered_set<ListNode*> temp;
    ListNode* curr = headA;
    while(curr)
    {
        temp.insert(curr);
        curr = curr -> next;
    }
    
    curr = headB;
    while(!temp.count(curr) && curr)
    {
        curr = curr->next;
    }
    if(curr)
    {
        return curr;
    }
    return nullptr;
 
}
//解法2
class Solution {
    public:
        ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
            if(headA == nullptr || headB == nullptr)
            {
                return nullptr;
            }
            ListNode* pa = headA;
            ListNode* pb = headB;
            while(pa!=pb)
            {
                pa=pa==nullptr?headB:pa->next;
                pb=pb==nullptr?headA:pb->next;
            }
            return pa;
            
            
        }
    };


int main()
{

    return 0;
}